Optical storage devices, such as CD-ROM, DVD, and the like, are used to store large amounts of audio, visual and/or computer data in a non-volatile manner. Sectors of data are typically recorded in spiral tracks on a rotating optical disk and, upon read back, the data are subject to errors due to noise and dynamics of the recording process. Accurate reproduction of corrupted data requires an error detection and correction (EDAC) system which implements an error correction code (ECC), such as a Reed-Solomon code. The EDAC system employed in optical storage devices is typically multi-layered meaning that user data are passed through a series of encoders which implement a series of ECC layers. Upon readback, the data is decoded according to the layered ECC in reverse order until error-free user data is ultimately extracted.
A typical data path employed in a CD-ROM type storage device is shown in FIG. 1. During a write operation, user data from a host is encoded 2 into a product code of P and Q code words having P.sub.ECC and Q.sub.ECC redundancy symbols, respectively. Data output by the P/Q encoder 2 is then scrambled 4 and the scrambled data passed through a C2 encoder 6 which processes the data in 24 byte blocks and attaches 4 bytes of C2 redundancy. The output of the C2 encoder 6 is then interleaved 8 into blocks of 28 bytes and the interleaved data passed through a C1 encoder 10 which attaches 4 bytes of C1 redundancy. The data is then written to the disk 12 in 32 byte blocks and, during read back, the process is run in reverse. The C1 and C2 redundancy are referred to as a Cross Interleave Reed-Solomon Code (CIRC).
During a read operation, the C1 decoder 10 decodes the 32 byte blocks read from the disk and corrects up to two bytes in error using the 4 bytes of C1 redundancy. If more than two errors are detected, then the C1 decoder 10 generates a C1 erasure pointer for each of the 32 bytes in the block. The C2 decoder 6 uses the C1 erasure pointers to assist in correcting the data output by the de-interleaver 8 (the C2 decoder can correct up to 4 bytes in error using up to four C1 erasure pointers and the 4 bytes of C2 redundancy). If the C2 decoder 6 successfully corrects a data block, then the C1 erasure pointers may be passed on as C2 erasure pointers. If a data block is uncorrectable, the C2 decoder sets a C2 erasure pointer for each of the 28 bytes in the block. The P/Q decoder 2 uses the C2 erasure pointers to assist in correcting the data output by the de-scrambler 4.
FIG. 2A shows a typical sector format employed in a CD-ROM storage device which comprises 2,352 bytes of information. The first 12 bytes store a sync mark 14 for use in byte synchronizing to the remaining data in the sector. The next 4 bytes store header information 16, such as the sector address and operating mode. The next 2048 bytes store the user data 18, which are followed by 4 bytes of CRC redundancy 20 and 8 pad bytes 22. The last 276 bytes store the P.sub.ECC and Q.sub.ECC redundancy 24A and 24B for the P and Q code words of the product code as shown in FIG. 2B. The P.sub.ECC and Q.sub.ECC redundancy 24A and 24B are generated by the P/Q encoder 2 of FIG. 1 during a write operation, and upon read back, used by the P/Q decoder 2 to detect and correct errors in the header 16, the user data 18, and the CRC bytes 20.
Operation of the P/Q encoder/decoder 2 is well known and is understood with reference to FIG. 2B. The data are arranged into two sets of intersecting code words: a set of P column code words, including appended P.sub.ECC redundancy; and a set of Q row code words, including appended Q.sub.ECC redundancy which are generated by processing the data diagonally as shown. During a read operation, the error correction process operates iteratively. A pass is made over the P code words, and then a pass is made over the Q code words, and then another pass is made over the P code words, and so on. If the number of errors in a P code word exceeds the error correction capability of the code, then the pass over the Q code words may correct enough errors such that the P code word becomes correctable in the next pass. Similarly, an uncorrectable Q code word may become correctable if enough errors are corrected during the pass over the P code words. Thus, the P/Q decoder 2 processes the P and Q code words in iterative passes until all of the code words are corrected, or until the number of iterations exceeds some predetermined maximum value (indicating that the sector is uncorrectable).
In addition to interleaving 8 the C2 encoded data as shown in FIG. 1, the P and Q product code of FIG. 2A may also be interleaved to form an EVEN and ODD product code as shown in FIG. 2C. In this format, the EVEN product code stores the even numbered bytes of a sector and the ODD product code stores the odd numbered bytes of a sector. Those skilled in the art understand that interleaving enhances the ability to correct a long burst error by spreading the error across multiple code words. In addition, interleaving the data into EVEN and ODD product codes enables the P/Q decoder 2 to correct two code words (two P or two Q) simultaneously, which significantly increases the throughput.
Increasing the throughput of the storage device is a significant design consideration. The speed of the P/Q decoder 2 is directly related to the number of buffer accesses required to read the P and Q code words, and the processing time required to correct a code word. In many prior art EDAC systems for processing a product code, all of the P and Q code words are read and processed during each iteration without regard to whether a code word may have been determined to be error-free or fully corrected in a prior iteration. U.S. Pat. No. 5,412,667 entitled "DECODER FOR CROSS INTERLEAVED ERROR CORRECTING ENCODED DATA" improves the speed of a product code processor in an optical storage device by "marking" code words as error-free. In this manner, the error-free code words are skipped during subsequent passes, which significantly increases the over all speed of the EDAC system. When errors are corrected in a particular code word (P or Q), only those code words which intersect at the corrected bytes are marked as containing errors so that their syndromes are recalculated during the next pass. Although this method is an improvement over processing all of the P and Q code words in every pass, it fails to take into account erasure pointers, such as those generated by the C2 decoder 6 or those generated internally. In other words, the '667 patent marks only those code words that intersect at corrected data bytes for processing during the next pass, without considering the significance of erasure pointers.
There is, therefore, a need for a more efficient EDAC system that takes into account erasure pointers (e.g., C2 erasure pointers) in determining whether to read and process a P or Q code word in a product code of an optical storage device.
Another aspect of the present invention concerns the CRC redundancy 20 shown in FIG. 2A, which is used to check the validity of the corrections made by the P/Q decoder 2 of FIG. 1. The CRC redundancy 20 is typically generated by processing the header and user data according to: EQU CRC redundancy=P(x).multidot.x.sup.n-k mod G(x),
where P(x) is the header and user data represented as a polynomial having coefficients in a finite field GF(2), n-k is the number of CRC redundancy symbols, and G(x) is a generator polynomial. The CRC redundancy 20 is then appended to the user data as shown in FIG. 2A before the resulting code word is written to the disk. During a read operation, the data read from the disk are processed to generate a CRC syndrome S.sub.CRC according to: EQU S.sub.CRC =C(x)mod G(x),
where C(x) is the data polynomial or code word (including the CRC redundancy) read from the disk. If the data C(x) is error-free, then the syndrome S.sub.CRC will be zero. By generating the CRC syndrome after the P/Q encoder 2 has finished correcting the product code, the CRC operates to validate the P/Q corrections and detect miss-corrections. This is an extremely important function because it prevents the EDAC system from passing "bad data" to the host system.
Generating the CRC syndrome S.sub.CRC after the P/Q decoder 2 finishes correcting the product code requires that all of the data be read from the buffer. This overhead can significantly reduce the overall throughput of the EDAC system but, as disclosed in U.S. Pat. No. 5,592,498 entitled "CRC/EDC CHECKER SYSTEM," it can be avoided. In the '498 patent, the CRC syndrome S.sub.CRC is generated concurrent with the processing of the P and Q code words. In the first pass of the P code words, a tentative CRC syndrome S.sub.CRC is generated, and then when the P/Q decoder makes a correction, the CRC syndrome S.sub.CRC is simultaneously updated to reflect the correction. In this manner, when the P/Q decoder 2 is finished processing each pass of the product code, the CRC syndrome S.sub.CRC is available immediately to check whether the corrections are valid and complete. However, the CRC generator disclosed in the '498 patent will not operate correctly with a P/Q decoder 2 that skips certain P or Q code words; rather, it only operates with a P/Q decoder 2 that reads all of the P and Q code words in every pass.
Another disadvantage with prior art P/Q decoders is the delay associated with determining whether the product code has been fully corrected. Because the prior art P/Q decoders do not generate the CRC syndrome S.sub.CRC concurrent with correcting the product code, they must make an additional pass to determine if in fact the corrections are complete. If, for example, no uncorrectable errors are encountered after completing a pass over the P code words, the prior art P/Q decoders perform another pass over the Q code words to verify that the corrections are in fact complete (i.e., to verify that the Q syndromes are all zero). Thus, prior art P/Q decoders will not generate the CRC syndrome S.sub.CRC for checking the validity of the corrections until all zero syndromes are generated for a P or Q pass--which is inefficient.
There is, therefore, a need for a CRC syndrome generator that can compute the CRC syndrome S.sub.CRC concurrent with the P/Q decoder 2 processing the product code, even if the P/Q decoder 2 skips a code word. Another object of the present invention is to avoid the additional pass required in the prior art EDAC systems to verify that the corrections are complete, as well as to avoid the additional pass required to generate the CRC syndrome S.sub.CRC.